package j2025.j04;

/**
 * @Author 猫大仙
 */
public class j0407 {
    public int minDistance(String word1, String word2) {
        // 获取 word1 和 word2 的长度
        int m = word1.length(), n = word2.length();

        // 如果其中一个单词为空，那么编辑距离就是另一个单词的长度
        if(m * n == 0) return m + n;

        // 创建一个二维数组 dp 来存储子问题的解
        int[][] dp = new int[m + 1][n + 1];

        // 初始化 dp 数组的第一列
        // dp[i][0] 表示将 word1 的前 i 个字符转换为空字符串所需的操作次数，即删除 i 次
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        // 初始化 dp 数组的第一行
        // dp[0][j] 表示将空字符串转换为 word2 的前 j 个字符所需的操作次数，即插入 j 次
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // 填充 dp 数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 考虑删除操作：将 word1 的前 i-1 个字符转换为 word2 的前 j 个字符，然后删除 word1 的第 i 个字符
                int left = dp[i - 1][j] + 1;

                // 考虑插入操作：将 word1 的前 i 个字符转换为 word2 的前 j-1 个字符，然后插入 word2 的第 j 个字符
                int right = dp[i][j - 1] + 1;

                // 考虑替换操作：将 word1 的前 i-1 个字符转换为 word2 的前 j-1 个字符
                int mid = dp[i - 1][j - 1];

                // 如果 word1 的第 i 个字符和 word2 的第 j 个字符不相等，则需要进行替换操作，操作次数加 1
                if(word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    mid += 1;
                }

                // 取三种操作中的最小操作次数
                dp[i][j] = Math.min(Math.min(left, right), mid);
            }
        }

        // 返回将 word1 的前 m 个字符转换为 word2 的前 n 个字符所需的最少操作次数
        return dp[m][n];
    }
}
